package com.leetcode.algorithm.y22.m07.w4;

/**
 * 43. 字符串相乘
 * 
 * https://leetcode.cn/problems/multiply-strings/
 * 
 * @author jie.deng
 *
 */
class Question0043Solution01 {
	
	public String multiply(String num1, String num2) {
		if ("0".equals(num1) || "0".equals(num2)) {
			return "0";
		}
		int len1 = num1.length();
		int len2 = num2.length();
		int[] arr1 = new int[len1];
		for (int i = 0; i < len1; i++) {
			arr1[i] = num1.charAt(i) - '0';
		}
		int[] arr2 = new int[len2];
		for (int i = 0; i < len2; i++) {
			arr2[i] = num2.charAt(i) - '0';
		}
		int[] arr3 = new int[len1 + len2 - 1];
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				arr3[i + j] += arr1[i] * arr2[j];
			}
		}
		int carry = 0;
		for (int i = arr3.length - 1; i > 0; i--) {
			int sum = arr3[i] + carry;
			arr3[i] = sum % 10;
			carry = sum / 10;
		}
		arr3[0] += carry;
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < arr3.length; i++) {
			builder.append(arr3[i]);
		}
		return builder.toString();
	}
    
}